\documentclass[12pt,UTF8]{ctexart}
\title{\textbf{最优化理论与算法课程第1次作业}}
\author{马哲辉}
\date{\today}
\usepackage[left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}

\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{ulem}
\usepackage{amssymb}
\usepackage{float}


\begin{document}
\maketitle

\tableofcontents
\begin{center}
\includegraphics[scale=0.6]{题目.png}
\end{center}

\section{5x1+4x2}
\subsection{图示法}
\begin{center}
\includegraphics[scale = 0.8]{图示法1.png}
\end{center}

如图所示，最优解为$x_1 = \frac{12}{7},x_2=\frac{15}{7},f = \frac{120}{7}$。
\subsection{基本可行解}
\begin{align*} 
    \begin{bmatrix} 
        -2 & 1\\
        1 &2\\
        5 &3\\
        1 &0\\
        0 &1
    \end{bmatrix}
    \begin{bmatrix}
        x_1\\
        x_2 
    \end{bmatrix} &= \begin{bmatrix}
        -4\\6\\15\\0\\0
    \end{bmatrix}\\
    B_1 = \begin{bmatrix} -2 & 1 \\1 &2\end{bmatrix};
    B_2 &= \begin{bmatrix} 1 &2 \\ 5 & 3\end{bmatrix};
    B_3 = \begin{bmatrix} -2 &1 \\ 5 &3\end{bmatrix}\\
    X_1 = \begin{bmatrix} 2.8\\1.6\end{bmatrix};
    X_2 &= \begin{bmatrix} \frac{27}{11}\\ \frac{10}{11} \end{bmatrix};
    X_3 = \begin{bmatrix} \frac{12}{7}\\ \frac{15}{7} \end{bmatrix}\\
    F_1 = 20.4;F_2 &=\frac{175}{11};F_3 = \frac{120}{7} \\
    5 \times 2.8+3 \times 1.6 &= 18.8>15,\mbox{不满足条件3}
\end{align*}
\begin{align*} 
    -2 \times \frac{27}{11}+\frac{10}{11}&=4,\mbox{满足条件1}\\
    \frac{12}{7}+2\times \frac{15}{7} &=6 \mbox{满足条件2}\\
  F_{max} &= F_3 = \frac{120}{7}
\end{align*}


\subsection{单纯形方法}

\begin{align*} 
  \begin{bmatrix} 
      -2 & 1\\
      1 &2\\
      5 &3
  \end{bmatrix}
  \begin{bmatrix}
      x_1\\
      x_2 
  \end{bmatrix} &= \begin{bmatrix}
      -4\\6\\15
  \end{bmatrix}\\
\end{align*}
由于约束数量大于变量数，因此需要增加松弛变量$s_1,s_2,s_3$构建：
\begin{align*} 
  \begin{bmatrix} 
      2 & -1&1&0&0\\
      1 &2&0&1&0\\
      5 &3&0&0&1
  \end{bmatrix}
  \begin{bmatrix}
      x_1\\
      x_2\\
      s_1\\
      s_2\\
      s_3
  \end{bmatrix} &= \begin{bmatrix}
      4\\6\\15
  \end{bmatrix}\\
\end{align*}

既而构建单纯形表：

\begin{table}[!htb]
  \begin{center}
    \caption{单纯形表}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
      \hline
      基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
      \hline
      $s_1$&0&2&-1&1 &0 &0 &4&2\\
      \hline
      $s_2$&0&1&2&0 &1 &0 &6&6\\
      \hline
      $s_3$&0&5&3&0 &0 &1 &15&3\\
      \hline
      z&-&5&4&0 &0 &0 &-&-\\
      \hline
    \end{tabular}\\
    
  \end{center}
\end{table}

5大于4,故取$x_1$为基，2最小，故$s_1$出基。

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
  \hline
  基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
  \hline
  f&-&5&4&0&0 &0 &- &-\\
  \hline
  $x_1$&5&1&-0.5&0.5 &0 &0 &2&-4\\
  \hline
  $s_2$&0&0 &2.5 &-0.5 &1 &0 &4&1.6\\
  \hline
  $s_3$&0&0 &5.5 &-2.5 &0 &1 &5&$\frac{10}{11}$\\
  \hline
  z&-&0&6.5&-2.5 &0 &0 &-&-\\
  \hline
\end{tabular}\\
\end{center}

6.5最大，故$x_2$进基，$\frac{10}{11}$最小，故$s_3$出基

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
  \hline
  基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
  \hline
  f&-&5&4&0&0 &0 &- &-\\
  \hline
  $x_1$&5 &1 &0 &$\frac{3}{11}$ &0 &$\frac{1}{11}$ &$\frac{27}{11}$&9\\
  \hline
  $s_2$&0 &0 &0 &$\frac{7}{11}$ &1 &-$\frac{5}{11}$ &$\frac{19}{11}$&$\frac{19}{7}$\\
  \hline
  $x_2$&$4$&0 &1 &$-\frac{5}{11}$ &0 &$\frac{2}{11}$ &$\frac{10}{11}$&-2\\
  \hline
  z&-&0&0&$\frac{5}{11}$ &0 &-$\frac{13}{11}$ &-&-\\
  \hline
\end{tabular}\\
\end{center}

$\frac{5}{11}>0$，故$s_1$进基，$\frac{19}{7}$小于$9$，故$s_2$出基

\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
    \hline
    基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
    \hline
    f&-&5&4&0&0 &0 &- &-\\
    \hline
    $x_1$&5 &1 &0 &0 &-$\frac{3}{7}$ &$\frac{2}{7}$ &$\frac{12}{7}$&-\\
    \hline
    $s_1$&0 &0 &0 &1 &$\frac{11}{7}$ &-$\frac{5}{7}$ &$\frac{19}{7}$&-\\
    \hline
    $x_2$&4 &0 &1 &0 &$\frac{5}{7}$ &-$\frac{1}{7}$ &$\frac{15}{7}$&-\\
    \hline
    z&-&0&0&0 &-$\frac{5}{7}$ &-$\frac{6}{7}$ &-&-\\
    \hline
  \end{tabular}\\
  \end{center}

此时，所有的判别值均小于0，因此，最优解为$x_1 = \frac{12}{7},x_2 = \frac{15}{7}$,
$$
5 \times x_1 +4 \times x_2 = \frac{120}{7}
$$

\subsection{整数规划}
根据之前的线性规划求解，可得非整数最优解为$x_1 = \frac{12}{7},x_2 = \frac{15}{7}$,根据$x_1$进行分枝。
\begin{align*} 
x_1 = 1+\frac{5}{7}\\
\mbox{当}x_1\leq 1 \mbox{时，有：}
\end{align*}
\begin{center} 
\includegraphics[scale = 0.8]{图示法1.1.png}
\end{center}

此时，最优解为$x_1 = 1,x_2 = 2.5,f = 15$。

当$x_1 \geq 2$时，有：
\begin{center} 
  \includegraphics[scale = 0.8]{图示法1.2.png}
\end{center}

此时，最优解为$x_1 = 2,x_2 = \frac{5}{3},f = \frac{80}{3}$。

\begin{align*}
  15 &< \frac{80}{3}\\
\end{align*}
因此对解$x_1 = 2,x_2 = \frac{5}{3}$进行分枝

当$x_2 \leq 1$时，有
\begin{center} 
  \includegraphics[scale = 0.8]{图示法1.3.png}
\end{center}

此时，最优解为$x_1 = 2.4,x_2 = 1,f = 16$。

当$x_1 \leq 2$时，无可行解

在当前范围内仅有1个整数解即$x_1 = 2,x_2 =1,f = 14$

$f_{4} = 14$



\section{生活问题}
假设你是一名营养师，你需要为客户设计一份饮食计划，使其既健康又经济。
你有两种食物可以选择，每种食物都有不同的营养成分和成本。
你需要确保客户摄入足够的蛋白质和纤维素，同时花费不超过一定的预算。

你有两种食物可供选择：苹果和香蕉。苹果每单位的价格为2元，香蕉每单位的价格为1元。
每单位苹果含有3克蛋白质和1克纤维素，每单位香蕉含有1克蛋白质和2克纤维素。
客户每天至少需要摄入6克蛋白质和4克纤维素，同时每天的食品预算不超过10元。

\begin{align*}
  min z &= 2 x_1 + x_2\\
  2 x_1 + x_2 &\leq 10 \mbox{(预算限制)}\\
  3 x_1 + x_2 &\geq 6 \mbox{(蛋白质限制)}\\
  x_1 + 2 x_2 &\geq 4 \mbox{(纤维素限制)}\\
  x_1,x_2 &\geq 0  \mbox{(非负)}
\end{align*}

\subsection{图示法}

\begin{center} 
  \includegraphics[scale = 0.8]{图示法2.png}
\end{center} 

$x_1 = 1.6,x_2 = 1.2,f_{min} = 4.4$

\subsection{基本可行解}

\begin{align*} 
  \begin{bmatrix} 
      2 & 1\\
      3 &1\\
      1 &2\\
      1 &0\\
      0 &1
  \end{bmatrix}
  \begin{bmatrix}
      x_1\\
      x_2 
  \end{bmatrix} &= \begin{bmatrix}
      10\\6\\4\\0\\0
  \end{bmatrix}\\
  B_1 = \begin{bmatrix} 2 & 1 \\3 &1\end{bmatrix};
  B_2 &= \begin{bmatrix} 2 &1 \\ 1 & 2\end{bmatrix};
  B_3 = \begin{bmatrix} 3 &1 \\ 1 &2\end{bmatrix}\\
  X_1 = \begin{bmatrix} -4\\18\end{bmatrix};
  X_2 &= \begin{bmatrix} \frac{16}{3}\\ -\frac{2}{3} \end{bmatrix};
  X_3 = \begin{bmatrix} 1.6\\ 1.2 \end{bmatrix}\\
  X_1,X_2 &\mbox{不满足非负约束}\\
  f_{min} &= F_3 = 4.4
\end{align*}

\subsection{单纯形方法}

\begin{align*} 
  \begin{bmatrix} 
      2 & 1\\
      3 &1\\
      1 &2
  \end{bmatrix}
  \begin{bmatrix}
      x_1\\
      x_2 
  \end{bmatrix} &= \begin{bmatrix}
      10\\6\\4
  \end{bmatrix}\\
\end{align*}
由于约束数量大于变量数，因此需要增加松弛变量$s_1,s_2,s_3$构建：
\begin{align*} 
  \begin{bmatrix} 
      -2 & -1&1&0&0\\
      1 &2&0&1&0\\
      5 &3&0&0&1
  \end{bmatrix}
  \begin{bmatrix}
      x_1\\
      x_2\\
      s_1\\
      s_2\\
      s_3
  \end{bmatrix} &= \begin{bmatrix}
      -10\\6\\4
  \end{bmatrix}\\
\end{align*}

既而构建单纯形表：

  \begin{center}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
      \hline
      基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
      \hline
      $s_1$&0&-2&-1&1 &0 &0 &-10&5\\
      \hline
      $s_2$&0&3&1&0 &1 &0 &6&2\\
      \hline
      $s_3$&0&1&2&0 &0 &1 &4&4\\
      \hline
      z&-&2&1&0 &0 &0 &-&-\\
      \hline
    \end{tabular}\\

  \end{center}

2大于1,故取$x_1$为基，2最小，故$s_2$出基。

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
  \hline
  基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
  \hline
  f&-&2&1&0&0 &0 &- &-\\
  \hline
  $s_1$&0&0&-$\frac{1}{3}$&1 &$\frac{2}{3}$ &0 &-6&18\\
  \hline
  $x_1$&2&1 &$\frac{1}{3}$ &0 &$\frac{1}{3}$ &0 &2&6\\
  \hline
  $s_3$&0&0 &$\frac{5}{3}$ &0 &-$\frac{1}{3}$ &1 &2&$1.2$\\
  \hline
  z&-&0&$\frac{1}{3}$&0 &-$\frac{2}{3}$ &0 &-&-\\
  \hline
\end{tabular}\\
\end{center}

$\frac{1}{3}>0$，故$x_2$进基，1.2最小，故$s_3$出基

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
  \hline
  基 &c& $x_1$ & $x_2$&$s_1$&$s_2$&$s_3$&右端&$\theta$ \\
  \hline
  f&-&2&1&0&0 &0 &- &-\\
  \hline
  $s_1$&0 &0 &0 &1 &$\frac{3}{5}$ &$\frac{1}{5}$ &-$\frac{28}{5}$ &$\frac{28}{3}$\\
  \hline
  $x_1$&2 &1 &0 &0 &$\frac{2}{5}$ &-$\frac{1}{5}$ &$\frac{8}{5}$&-4\\
  \hline
  $x_2$&1 &0 &1 &0 &-$\frac{1}{5}$ &$\frac{3}{5}$&$\frac{6}{5}$ &-6\\
  \hline
  z&-&0&0&0 &-$\frac{3}{5}$ &-$\frac{1}{5}$ &-&-\\
  \hline
\end{tabular}\\
\end{center}

此时，所有的判别值均小于0，因此，最优解为$x_1 = \frac{8}{5},x_2 = \frac{6}{5}$,
$$
2 \times x_1 +1 \times x_2 = 4.4
$$

\subsection{整数规划}
根据之前的线性规划求解，可得非整数最优解为$x_1 = 1.6,x_2 = 1.2$,根据$x_1$进行分枝。
当$x_1 \leq 1$时，有：
\begin{center} 
  \includegraphics[scale = 0.8]{图示法2.1.png}
\end{center}

此时，最优解为$x_1 = 1,x_2 = 3,f = 5$。

当$x_1 \geq 2$时，有：
\begin{center} 
  \includegraphics[scale = 0.8]{图示法2.2.png}
\end{center}

此时，最优解为$x_1 = 2,x_2 = 1,f = 5$。

因此2个解均为最优解


\end{document}